<?php
/**
 * @title 5472. 重新排列字符串 - 原地互换
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @param Integer[] $indices
     * @return String
     */
    function restoreString($s, $indices) {
        /**
         * @since 2020-10-21 长度
         */
        $len = count($indices);

        /**
         * @since 2020-10-21 迭代
         */
        for($i=0; $i<$len; $i++){
            if($i != $indices[$i]){
                /**
                 * @since 2020-10-21 位置错误, 需要互换
                 * @since 2020-10-21 char1=s[b], s[b]=char, char=char1
                 */
                $a = $i;
                $char = $s[$a];

                /**
                 * @since 2020-10-21 直到回到`i`停止
                 */
                do{
                    $b = $indices[$a];
                    list($char, $s[$b]) = [$s[$b], $char];
                    $indices[$a] = $a;
                    $a = $b;
                    // echo "a={$a}, char={$char}, s={$s}", PHP_EOL;
                }while($b != $i);

                /**
                 * @since 2020-10-21 回到起点
                 */
                $indices[$i] = $i;
            } else {
                /**
                 * @since 2020-10-21 不需要互换
                 */
            }
        }

        /**
         * @return
         */
        return $s;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.26_6.php
 */
$datas = [
    ["codeleet",[4,5,6,7,0,2,1,3]],
    ["abc", [0,1,2]],
    ["aiohn", [3,1,4,2,0]],
    ["aaiougrt", [4,0,2,6,7,3,1,5]],
    ["art", [1,0,2]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->restoreString($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
